package array

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnumcr/
// 合并两个有序数组
// 算法: 遍历
// 时间复杂度: O(n)
func Merge(nums1 []int, m int, nums2 []int, n int) {
	// 先拷贝数组nums1 空间换时间
	tempNums1 := make([]int, m)
	copy(tempNums1, nums1[:m])

	index1, index2 := 0, 0
	indexRetArr := 0
	for index1 < m || index2 < n {
		if index1 >= m || (index2 < n && nums2[index2] < tempNums1[index1]) {
			nums1[indexRetArr] = nums2[index2]
			index2++
		} else {
			nums1[indexRetArr] = tempNums1[index1]
			index1++
		}
		indexRetArr++
	}
}

// 更省空间的 O(n + m) 算法
// 算法: 逆向指针覆盖 nums1 数组。因为比较大的数一定先遍历到，所以在低位的数不用担心被覆盖
func MergeWithTwoPointer(nums1 []int, m int, nums2 []int, n int) {
	left, right := m-1, n-1
	tail := m + n - 1
	var currentNum int
	for tail >= 0 {
		if left < 0 {
			currentNum = nums2[right]
			right--
		} else if right < 0 {
			currentNum = nums1[left]
			left--
		} else if nums1[left] >= nums2[right] {
			currentNum = nums1[left]
			left--
		} else {
			currentNum = nums2[right]
			right--
		}
		nums1[tail] = currentNum
		tail--
	}
}
